/*
 * @lc app=leetcode.cn id=106 lang=golang
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// 1. 递归
// 中序遍历：左子树的中序遍历结果, 根节点, 右子树的中序遍历结果
// 后序遍历：左子树的后序遍历结果, 右子树的后序遍历结果，根节点
// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}

	i := 0
	for ; inorder[i] != postorder[len(postorder)-1]; i++ {
	}

	left := buildTree(inorder[:i], postorder[:i])
	right := buildTree(inorder[i+1:], postorder[i:len(postorder)-1])

	return &TreeNode{postorder[len(postorder)-1], left, right}
}

// @lc code=end

